Data networks are formed of a number of network elements (NEs) interconnected by links. The links interconnecting the NEs may form a pattern corresponding to one of a number of known topologies, such as ring, star, linear, and full mesh topologies. A class of topologies called mesh networks is a generalization of these topologies and is associated with no restrictions on links (except that every NE is directly or indirectly interconnected to every other NE via some number of links and intermediate (NEs). It is further commonplace in today's networks to find different autonomously managed networks bridged to each other at various gateways and for data transport services to be provided across the networks in a manner that is transparent to users.
Typically, core networks are fed by edge networks, the core network serving to interconnect disparate edge networks, and generally providing longer haul data transport. In recent years for numerous reasons, including security, privacy, scalability, and simplicity, core network providers have recognized a value for presenting abstracted representations of their topologies to edge network NEs. Frequently the core network is abstracted to represent a full mesh network (where each abstracted NE is linked to each other abstracted NE). Such an abstracted network typically includes only the NEs relevant to the edge network, which may be every core NE that is linked to an edge network NE, or a subset of those core NEs.
As noted, one of the reasons for presenting the abstracted view of the core network is that many complicated details of allowable routes and network availability are simplified. For example, many core networks have a ring topology, such as a synchronous optical network (SONET) ring, and many of these rings networks impose timeslot continuity restrictions on allowable paths. Timeslot continuity is a requirement that traffic conveyed over successive links of the ring must occupy the same timeslot on successive links. Where timeslot continuity is not available, traffic cannot be routed through the adjacent links in sequence, even though each link, taken alone, has sufficient capacity to carry the traffic. Such a problem introduces a constraint in computing paths through the abstracted core, because it is possible that capacity is available over a route AB between A and B and a route BC between B and C, but traffic cannot transit AB and then BC in sequence. Such a constraint is termed “subnetwork intransitivity”, because transitivity (a well known mathematical property of relations asserting that for any A,B,C, if A is related to B, and B is related to C, then A is related to C) of the network fails if each of routes AB and BC are individually allowable but path ABC (traversing routes AB and BC in sequence) is not allowable, in the same subnetwork.
Similar subnetwork intransitivity is encountered in passive optical networks where wavelength continuity is required. In passive optical networks no optical fiber link of the passive optical network can transport traffic on two channels at the same wavelength. Accordingly a wavelength channel may be available on a first optical fiber link, and a second wavelength channel may be available on a second link, but it is not possible to transmit a signal over the two links in sequence.
A third example of subnetwork intransitivity is found in core networks that do not require wavelength or timeslot continuity, but have abstracted views that are updated in response to changes in availability of the actual resources of the network. Generally in such networks a change in availability (e.g. caused by signal failures, a threshold of occupancy is exceeded, etc.) is signaled by a tandem NE within the core network using a flooding process well known in the art. This method is effective for delivering the change of availability information to an edge networks, but it does not guarantee that the information received by the edge network is either consistent or timely. It can take a second between receiving a first update and receiving consistent information regarding the network. In the interim an apparently allowable route may be tried unsuccessfully many times. Each unsuccessful attempt uses NE processor time, and congests network control signaling channels to no avail. This problem is referred to as “buzzing”.
In the first example of subnetwork intransitivity (timeslot continuity), an allowable path may be obtained by exiting the subnetwork and returning to it. For example, traffic may leave the ring and re-enter on a different timeslot to obtain an allowable path, because timeslot continuity is only required between successive links within the ring itself. Following the above example, in which routes AB and BC are individually allowable but path ABC (that is, routes AB and BC in sequence) is not allowable, path ABDBC (traversing routes AB, BD, DB, BC in sequence) would be an allowable path, provided that routes BD and DB have available bandwidth and D is not in the subnetwork. Similarly, if leaving the passive optical network core involves receiving the optical channel and reemitting the signal at another wavelength, the excursion from the core network may make the path allowable.
However, the third example (and the second example where reception of the optical channel is not an option) are examples of a stronger constraint on acceptable routes in the network. Broadly stated, the “stronger constraint” refers to a case where, for example, a path that traverses route AB cannot allowably be extended through route BC, even with a detour through a node D that is not part of the subnetwork. Thus, the “stronger constraint” would mean that neither or paths ABC or ABDBC would be allowable, because the path traverses route AB, and so cannot be extended through route BC, even with the intermediate detour through routes BD and DB. One method for solving subnetwork intransitivity is taught in co-pending, co-assigned U.S. patent application Ser. No. 10/691,517, entitled METHOD AND APPARATUS FOR DERIVING ALLOWABLE PATHS THROUGH A NETWORK WITH INTRANSITIVITY CONSTRAINTS which was filed on Oct. 24, 2003 and is incorporated herein by reference. Both subnetwork intransitivity and the stronger constraint give rise to what are termed “subset sequence constraints”.
While numerous methods for computing routes using variants of Dijkstra's algorithm, artificial intelligence applications, and linear programming methods, are known, none of these methods provides paths that are guaranteed to be optimal allowable paths, and none of these accounts for subset sequence constraints.
There therefore exists a need for a method and apparatus for computing optimal paths subject to a subset sequence constraint.